package ch4tree;

import java.util.HashMap;

public class Ex5 {

	public static TreeNode successor(TreeNode x) {
		if (x.right != null) {
			TreeNode n = x.right;
			while (n.left != null) {
				n = n.left;
			}
			return n;
		}
		else {
			TreeNode n = x;
			while (n.parent != null) {
				TreeNode p = n.parent;
				if (n == p.left) {
					return p;
				}
				else {
					n = p;
				}
			}
			return null;
		}
	}

	public static void main(String... argv) {
		HashMap<Integer, TreeNode> bst = Chapter.createMinimalBST(new int[] { 1, 2, 3, 4, 5, 6 }, true);
		TreeNode root = bst.get(3);
		BTreePrinter.printNode(root);
		for (int key : bst.keySet()) {
			System.out.println("successor of "+key+" is "+successor(bst.get(key)));
//			System.out.println(bst.get(4).parent);
		}
		int a = 1;
	}
}
